// class Solution {
//     public int tribonacci(int n) {
//         // 判断特殊情况
//         if (n == 0) {
//             return 0;
//         }
//         if (n == 1 || n == 2) {
//             return
//         }
//         // dp数组用来存放数，dp[i]表示第i个泰波那契数
//         int[] dp = new int[n+1];
//         dp[0] = 0; // n可能为0
//         dp[1] = 1;
//         dp[2] = 1;
//         for (int i = 3; i <= n; i++) {
//             dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
//         }
//         return dp[n];
//     }
// }


class Solution {
    public int tribonacci(int n) {
        // 判断特殊情况
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int sum = a + b + c;
            a = b;
            b = c;
            c = sum;
        }
        return c;
    }
}